import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Created by LLAP on 2018/1/8.
 * Copyright (c) 2017 LLAP. All rights reserved.
 */
public class Metro {
    public ArrayList<Station> stations;
    private ArrayList<LinkedList<Path>> graph;

    private static class Path {
        int target;
        double dis;
        public Path() {}
        public Path(int t, double d) {
            target = t;
            dis = d;
        }
        @Override
        public String toString() {
            return "Path{" + "target=" + target + ", dis=" + dis + '}';
        }
    }

    public Metro() {
        stations = new ArrayList<>();
        graph = new ArrayList<>();
    }

    public Station get(int index) {
        return stations.get(index);
    }

    public Station add(Station s) {
        s.setId(stations.size());
        stations.add(s);
        graph.add(new LinkedList<>());
        return s;
    }

    public void add(Station[] s) {
        for (Station t : s) {
            this.add(t);
        }
    }

    public void addPath(int from, int to, double dis) {
        graph.get(from).addFirst(new Path(to, dis));
        graph.get(to).addFirst(new Path(from, dis));
    }

    public Result find(Station from, Station to) {
        return this.find(from.getId(), to.getId());
    }

    private Result find(int from, int to) {
        Result ret = new Result();
        ret.dis = Double.MAX_VALUE;
        ret.count = Integer.MAX_VALUE;
        boolean[] vis = new boolean[stations.size()];
        find(ret, vis, from, to, 0, 0, "");
        if (ret.dis < Double.MAX_VALUE) {
            ret.price = getPrice(ret.dis);
        }
        return ret;
    }


    private void find(
            Result result,
            boolean[] vis,
            int from, int to,
            double dis,
            int count,
            String paths) {
        find(result, vis, from, to, dis, count, paths, false);
    }
    private void find(
            Result result,
            boolean[] vis,
            int from, int to,
            double dis,
            int count,
            String paths,
            boolean interChange) {
        if (vis[from]) return;
        if (!interChange) paths += stations.get(from).getName();
        if (from == to) {
            count++;
            if (dis <= result.dis) {
                result.dis = dis;
                if (count <= result.count) {
                    result.count = count;
                    result.path = paths;
                }
            }
            return;
        }
        vis[from] = true;
        for (Path i : graph.get(from)) {
            if (!interChange) {
                if (i.dis > 0) {
                    find(result, vis, i.target, to,
                            dis + i.dis, count + 1, paths + "->");
                }
                else {
                    if (i.target != to) find(
                            result, vis, i.target, to, dis, count,
                            paths + "->换乘" +
                                    stations.get(i.target).getLine() + "->",
                            true);
                    else find(result, vis, i.target, to,
                            dis, count, paths, true);
                }

            }
            else {
                if (i.dis > 0) find(result, vis, i.target, to,
                        dis + i.dis, count + 1, paths);
            }
        }
        vis[from] = false;
    }

    public int getPrice(double dis) {
        if (dis <= 10) return 2;
        if (dis <= 16) return 3;
        if (dis <= 22) return 4;
        if (dis <= 30) return 5;
        if (dis <= 38) return 6;
        if (dis <= 48) return 7;
        if (dis <= 58) return 8;
        if (dis <= 70) return 9;
        return 9 + (int)((dis - 70) / 14);
    }

}
